/**
 * Copyright (C) 2012 Daniel Gee.
 * See LICENSE.txt for more details.
 */
package com.rl.dungeon.builders;

import java.awt.Rectangle;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import com.rl.dungeon.Direction;
import com.rl.dungeon.DungeonTerrain;
import com.rl.dungeon.Location;
import com.rl.util.DiceRoller;

/**
 * Generates a DungeonTile[][] to build a dungeon with.
 * 
 * @author Daniel Gee
 */
public class DefaultBuilder
{
	/**
	 * Odds that an already connected room will get connected again.
	 */
	private int chanceOfReconnect = 75;

	/**
	 * The DiceRoller used for randomization.
	 */
	private final DiceRoller diceRoller;

	/**
	 * The number of columns that the map space is split into.
	 */
	private int numColumns = 3;

	/**
	 * The number of rows that the map space is split into.
	 */
	private int numRows = 3;

	/**
	 * The chance of there being a room within a segment of the map.
	 */
	private int roomChance = 85;

	/**
	 * @param dr
	 *            the {@link DiceRoller} for this generator to use.
	 */
	public DefaultBuilder(DiceRoller dr)
	{
		this.diceRoller = dr;
	}

	/**
	 * @param width
	 *            the width of the new dungeon.
	 * @param height
	 *            the height of the new dungeon.
	 * @return a new 2d array of terrain.
	 */
	public DungeonTerrain[][] generate(int width, int height)
	{
		DungeonTerrain[][] dungeon = new DungeonTerrain[width][height];
		for (int x = 0; x < width; x++)
		{
			for (int y = 0; y < height; y++)
			{
				dungeon[x][y] = DungeonTerrain.Wall;
			}
		}

		int heightSegment = height / this.numColumns;
		int widthSegment = width / this.numRows;
		/**
		 * We'll use this to track the rooms and their orientation with one another.
		 */
		Rectangle[][] roomGrid = new Rectangle[this.numColumns][this.numRows];

		// System.out.println("Rolling for new rooms...");
		for (int segX = 0; segX < this.numColumns; segX++)
		{
			for (int segY = 0; segY < this.numRows; segY++)
			{
				/**
				 * Determine bounds for this segment.
				 */
				int minX = Math.max(segX * widthSegment, 1);
				int minY = Math.max(segY * heightSegment, 1);
				int maxX;
				int maxY;
				if (segX < this.numColumns - 1)
				{
					maxX = Math.max(segX * widthSegment, (segX + 1) * widthSegment);
				}
				else
				{
					maxX = Math.max(segX * widthSegment, width - 1);
				}
				if (segY < this.numRows - 1)
				{
					maxY = Math.max(segY * heightSegment, (segY + 1) * heightSegment);
				}
				else
				{
					maxY = Math.max(segY * heightSegment, height - 1);
				}
				/**
				 * Determine contents of this segment and add it to the list. Segments "without" a
				 * room need to still have a 1x1 location for the corridor connection process blow
				 * to work properly. The list needs to always have 1 element per segment.
				 */
				if (this.diceRoller.randInRange(1, 100) < this.roomChance)
				{
					// We're adding a room
					// // Start point is up to halfway along the possible space.
					// int rx = random(minX, (maxX - minX) / 2 + minX);
					// int ry = random(minY, (maxY - minY) / 2 + minY);
					// // End point is anywhere from there to the end of the space.
					// int rw = random(rx + minRoomWidth, maxX - minRoomWidth) - rx;
					// int rh = random(ry + minRoomHeight, maxY - minRoomHeight) - ry;
					// placeRoom(dungeon, rx, ry, rw, rh);
					// roomGrid[segX][segY] = new Rectangle(rx, ry, rw, rh);
					int rx1 = this.diceRoller.randInRange(minX, maxX);
					int rx2 = this.diceRoller.randInRange(minX, maxX);
					while (rx1 == rx2)
					{
						rx2 = this.diceRoller.randInRange(minX, maxX);
					}

					int ry1 = this.diceRoller.randInRange(minY, maxY);
					int ry2 = this.diceRoller.randInRange(minY, maxY);
					while (ry1 == ry2)
					{
						ry2 = this.diceRoller.randInRange(minY, maxY);
					}

					int rx = Math.min(rx1, rx2);
					int ry = Math.min(ry1, ry2);
					int rw = Math.max(rx1, rx2) - rx;
					int rh = Math.max(ry1, ry2) - ry;
					this.placeRoom(dungeon, rx, ry, rw, rh);
					roomGrid[segX][segY] = new Rectangle(rx, ry, rw, rh);
				}
				else
				{
					// We're adding a 1 tile "false room"
					int rx = this.diceRoller.randInRange(minX, (maxX - minX) / 2 + minX);
					int ry = this.diceRoller.randInRange(minY, (maxY - minY) / 2 + minY);
					this.placeRoom(dungeon, rx, ry, 1, 1);
					roomGrid[segX][segY] = new Rectangle(rx, ry, 1, 1);
				}
			}
		}

		// connect the segments so that no places are inaccessable.
		/**
		 * We use this to track which have been connected or not yet.
		 */
		boolean[][] connectedGrid = new boolean[this.numColumns][this.numRows];
		/**
		 * select a segment to start at, randomly.
		 */
		Location startPoint = Location.of(this.diceRoller.randInRange(0, connectedGrid.length - 1),
				this.diceRoller.randInRange(0, connectedGrid[0].length - 1));
		/**
		 * Since it's the starting segment, add it as being connected.
		 */
		connectedGrid[startPoint.x][startPoint.y] = true;

		this.floodConnect(dungeon, connectedGrid, roomGrid, startPoint);

		Location stairsLoc = this
				.pickRandomWithin(roomGrid[this.diceRoller.randInRange(0, 2)][this.diceRoller
						.randInRange(0, 2)]);
		dungeon[stairsLoc.x][stairsLoc.y] = DungeonTerrain.StairsDown;

		// return the results
		return dungeon;
	}

	/**
	 * Connects two rooms. The ordering of the rooms doesn't matter.
	 * 
	 * @param dungeon
	 *            the dungeon we'll be working with
	 * @param r1
	 *            the first room
	 * @param r2
	 *            the other room.
	 */
	private void connect(DungeonTerrain[][] dungeon, Rectangle r1, Rectangle r2)
	{
		// pick to spots to connect.
		Location a = this.pickRandomWithin(r1);
		Location b = this.pickRandomWithin(r2);
		// figure out how we get from a to b.
		Direction northOrSouth;
		Direction eastOrWest;
		if (a.y < b.y)
		{
			// a is north of b, so we'll be moving south as we move.
			northOrSouth = Direction.South;
		}
		else
		{
			// a is south of b, so we'll be going north.
			northOrSouth = Direction.North;
		}
		if (a.x < b.x)
		{
			// a is west of b, so we'll be going east.
			eastOrWest = Direction.East;
		}
		else
		{
			// a is east of b, so move west
			eastOrWest = Direction.West;
		}
		// figure out how far it is from a to b.
		int northOrSouthHowMany = Math.abs(a.y - b.y);
		int eastOrWestHowMany = Math.abs(a.x - b.x);
		// we start off going the direction that will take longer.
		// then we switch directions sometime in the middle.
		// then we go back once we're lined up and go to the end like that.
		Direction startDirection;
		int firstDirectionSteps;
		Direction otherDirection;
		int otherDirectionSteps;
		int finalSteps;
		if (northOrSouthHowMany > eastOrWestHowMany)
		{
			startDirection = northOrSouth;
			firstDirectionSteps = this.diceRoller.randInRange(0, northOrSouthHowMany);
			otherDirection = eastOrWest;
			otherDirectionSteps = eastOrWestHowMany;
			finalSteps = northOrSouthHowMany - firstDirectionSteps;
		}
		else
		{
			startDirection = eastOrWest;
			firstDirectionSteps = this.diceRoller.randInRange(0, eastOrWestHowMany);
			otherDirection = northOrSouth;
			otherDirectionSteps = northOrSouthHowMany;
			finalSteps = eastOrWestHowMany - firstDirectionSteps;
		}

		// Now do all that!
		while (firstDirectionSteps > 0)
		{
			a = startDirection.from(a);
			dungeon[a.x][a.y] = DungeonTerrain.Floor;
			firstDirectionSteps--;
		}
		while (otherDirectionSteps > 0)
		{
			a = otherDirection.from(a);
			dungeon[a.x][a.y] = DungeonTerrain.Floor;
			otherDirectionSteps--;
		}
		while (finalSteps > 0)
		{
			a = startDirection.from(a);
			dungeon[a.x][a.y] = DungeonTerrain.Floor;
			finalSteps--;
		}
	}

	/**
	 * FloodFill style connection of all the rooms once they're made.
	 * 
	 * @param d
	 *            the dungeon we'll be working with.
	 * @param connectedGrid
	 *            a boolean grid of which rooms are "connected" or not yet.
	 * @param roomGrid
	 *            the grid of rooms.
	 * @param start
	 *            the point to start the floodfill from.
	 */
	private void floodConnect(DungeonTerrain[][] d, boolean[][] connectedGrid,
			Rectangle[][] roomGrid, Location start)
	{
		// first we collect all the points we MIGHT go to from this point.
		List<Location> validPointsFromHere = new ArrayList<>();
		for (Direction dir : Direction.cardinals())
		{
			Location p = dir.from(start);
			if (p.x < 0 || p.x >= connectedGrid.length || p.y < 0 || p.y >= connectedGrid[0].length)
			{
				continue;
			}
			else
			{
				validPointsFromHere.add(p);
			}
		}
		// We shuffle the list so that the flood fill isn't always the same.
		Collections.shuffle(validPointsFromHere);
		// now we decide what to do with each point in the list.
		while (validPointsFromHere.size() > 0)
		{
			// get a valid point
			Location p = validPointsFromHere.get(0);
			validPointsFromHere.remove(0);
			// check if it's connected already or not.
			if (connectedGrid[p.x][p.y])
			{
				// if already connected, chance of making an extra connection!
				if (this.diceRoller.randInRange(1, 100) < this.chanceOfReconnect)
				{
					this.connect(d, roomGrid[start.x][start.y], roomGrid[p.x][p.y]);
				}
			}
			else
			{
				// if not connected, connect it, record that you did, and recurse.
				this.connect(d, roomGrid[start.x][start.y], roomGrid[p.x][p.y]);
				connectedGrid[p.x][p.y] = true;
				this.floodConnect(d, connectedGrid, roomGrid, p);
			}
		}
	}

	/**
	 * Selects a random point within a room.
	 * 
	 * @param r
	 *            the rectangle that represents the room.
	 * @return a random point within the room.
	 */
	private Location pickRandomWithin(Rectangle r)
	{
		int px = r.x + this.diceRoller.randInRange(0, r.width - 1);
		int py = r.y + this.diceRoller.randInRange(0, r.height - 1);
		return Location.of(px, py);
	}

	/**
	 * Carves a room into the dungeon.
	 * 
	 * @param dungeon
	 *            the dungeon we'll be working with.
	 * @param x
	 *            the x point of the room.
	 * @param y
	 *            the y point of the room.
	 * @param width
	 *            how wide the room is.
	 * @param height
	 *            how tall the room is.
	 */
	private void placeRoom(DungeonTerrain[][] dungeon, int x, int y, int width, int height)
	{
		for (int dx = 0; dx < width; dx++)
		{
			for (int dy = 0; dy < height; dy++)
			{
				dungeon[x + dx][y + dy] = DungeonTerrain.Floor;
			}
		}
	}
}
